备用返回通道

转到题目

题目描述

对于给定的由 n 个整数组成的数组 {a1, a2, ..., an}，小龙和小蛇借助于此数组进行游戏。

游戏步骤如下：

1. 小龙选择一个非空区间 [a, b]；
2. 小蛇选择一个非空区间 [c, d]；
3. 将选中的区间中的全部元素均乘上 k，得到数组 a'；

游戏只进行一轮，三个步骤结束后立即停止。小龙想要让数组 a' 的元素之和尽可能大，小蛇想要让数组 a' 的元素之和尽可能小。假设双方都采取的是最优策略，请你计算操作后得到的数组 a' 的元素之和。

注意：

• 区间 [a, b] 和 [c, d] 可以相交，但只结算一次，即若某一个位置被小龙和小蛇同时选中，依旧只乘一次。

输入描述

每个测试文件均包含多组测试数据。

• 第一行输入一个整数 T (1 ≤ T ≤ 100) 代表数据组数。
• 每组测试数据描述如下：
  • 第一行输入两个整数 n, k (1 ≤ n ≤ 10^5; −100 ≤ k ≤ 100) 代表数组中的元素数量和乘数。
  • 第二行输入 n 个整数 a1, a2, ..., an (-10^6 ≤ ai ≤ 10^6) 代表数组元素。

除此之外，保证单个测试文件的 n 之和不超过 2 × 10^5。

输出描述

对于每一组测试数据，新起一行。输出一个整数，代表操作后数组 a' 的元素之和。

示例1

输入

3
2 4
1 1
6 0
1 1 4 5 1 4
4 -1
-2 1 -10 3

输出

8
0
8

说明

• 对于第一组测试数据，小龙的最优策略是选择区间 [1, 2]，一旦这么做了，无论小蛇选择的区间是什么，都不会影响最终答案。
• 对于第三组测试数据，其中一种最优策略为：龙选择区间 [1, 3]，小蛇选择区间 [4, 4]。

题目思路:

• 小蛇想要a’尽可能的小
  • 但是如果他选区间，如果这个乘积数它是正数的话,那我就要乘以那个尽可能小的数
  • 如果这个乘积数它是负数的话,那我就要乘以那个尽可能大的数
• 小龙想要a’尽可能的大
  • 但是如果他选区间，如果这个乘积数它是正数的话,那我就要乘以那个尽可能大的数
  • 如果这个乘积数它是负数的话,那我就要乘以那个尽可能小的数
• 我们整理一下
  • 正数下:
    • 小龙选择尽可能大的区间
    • 小蛇选择尽可能小的区间
  • 负数下:
    • 小龙选择尽可能小的区间
    • 小蛇选择尽可能大的区间
• 而二者的操作是覆盖关系，也就是区间选取都有主导权。
• 最优策略下:
  • 如果在自己优势数下，要不给对手留机会
• 这样看，决定胜负的是操作数，因为每个人的优势数是互补的
• 我们这样根据操作数来算出来这个对局结果就行了